package link;

public class leetCode25_reverseKGroup {
    public static void main(String[] args) {
        leetCode25_reverseKGroup a = new leetCode25_reverseKGroup();
        ListNode b = new ListNode(1);
        b.next = new ListNode(2);
        b.next.next = new ListNode(3);
        b.next.next.next = new ListNode(4);
        b.next.next.next.next = new ListNode(5);
        a.reverseKGroup(b,2);
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素
        // 正因为这里b是开区间，才不需要搞个虚拟节点
        ListNode a = head;
        ListNode b = head;

        for (int i = 0; i < k; i++) {
            if(b == null) return head;
            b = b.next;
        }
        ListNode newHead = reverse(a,b);
        a.next = reverseKGroup(b,k);
        return newHead;

    }

    private ListNode reverse(ListNode a,ListNode b){
        if(a == null) return null;
        ListNode pre = null;
        ListNode cur = a;
        while (cur != b){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}